//
// Created by xili on 2024/9/10 10:43.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int> &arr, int k) {
        map<int, int> m;
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            m[arr[i]]++;
        }
        n = m.size();
        vector<int> v(n);
        int i = 0;
        for (auto &[x, c]: m) {
            v[i++] = c;
        }
        i = 0;
        int ans = 0;
        sort(v.begin(), v.end());
        while (k) {
            if (k - v[i] < 0 || ans == n) {
                break;
            } else {
                k -= v[i++];
                n--;
            }
        }
        return n;
    }
};